from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def generateMatrix(self, n):
        upper_bound, lower_bound = 0, n-1
        left_bound, right_bound = 0, n-1
        matrix = [[0 for _ in range(n)] for _ in range(n)]
        num = 1
        while num <= n**2:
            #顶部从左侧往右侧
            if upper_bound<=lower_bound:
                for j in range(left_bound, right_bound+1):
                    matrix[upper_bound][j] = num
                    num += 1
                upper_bound+=1
            # 右侧从上往下
            if left_bound<=right_bound:
                for j in range(upper_bound, lower_bound+1):
                    matrix[j][right_bound] = num
                    num+=1
                right_bound-=1
            #底部 从右往左
            if upper_bound<=lower_bound:
                for j in range(right_bound, left_bound-1,-1):
                    matrix[lower_bound][j] = num
                    num += 1
                lower_bound -= 1
            # 左侧从下往上
            if left_bound<=right_bound:
                for j in range(lower_bound, upper_bound-1,-1):
                    matrix[j][left_bound] = num
                    num += 1
                left_bound+=1
        return matrix

# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    print(solution.generateMatrix(3))
    # your test code here